import java.util.HashMap;
import java.util.Map;

/**
 * @author LKQ
 * @date 2022/2/18 14:18
 * @description
 */
public class Solution {
    public static void main(String[] args) {

    }

    /**
     * f(o) 代表选择o节点时，o节点的子树上被选择的节点的最大权值和，f(o) = g(l) + g(r)
     * g(o) 代表不选择o节点时，o节点的子树上被选择的节点的最大权值和，g(o) = max{f(l), g(l)} + max{f(r}, g(r)}
     */
    Map<TreeNode, Integer> f = new HashMap<>();
    Map<TreeNode, Integer> g = new HashMap<>();

    public int rob(TreeNode root) {
        dfs(root);
        return Math.max(f.getOrDefault(root, 0), g.getOrDefault(root, 0));
    }

    public void dfs(TreeNode node) {
        if (node == null) {
            return;
        }
        dfs(node.left);
        dfs(node.right);
        f.put(node, node.val + g.getOrDefault(node.left, 0) + g.getOrDefault(node.right, 0));
        g.put(node, Math.max(f.getOrDefault(node.left, 0), g.getOrDefault(node.left, 0)) + Math.max(f.getOrDefault(node.right, 0), g.getOrDefault(node.right, 0)));
    }

}
